Prepared by Talha Alvi and Farhan Wadia
There are various criteria, hard and soft constraints that can be considered in a delivery vehicle routing optimization problem. An additional criteria for routing would be route selection that minimizes fuel usage. This can be done by considering the average speeds along the route and using the delivery vehicle fuel consumption figures to calculate the most fuel efficient route. A hard constraint that can be considered is that the deliveries must co-incide with the opening hours of each place of business. This makes the problem even more challenging as separate time windows will need to be considered for each business. Other constraints include maximum weight or volume that can be carried by the delivery vehicle, before it may need to return to the warehouse to load more items. Another soft constraint would be to avoid certain routes during rush hour to minimize delivery times. A soft constraint that can be imposed on the problem is to avoid routing through school zones or residential zones to avoid creating congestion or creating noise pollution in quite areas.
import pandas as pd
# Import the dataset
df = pd.read_csv('GTA Delivery Dataset\GTA Delivery Data.csv')
# Obtain the unique collection (source) locations and how many dropoff locations each serves
collection_locations = df.groupby(['collection_lat', 'collection_lng']).size().reset_index().rename(columns={0:'Dropoff Locations Count'})
collection_locations
| collection_lat | collection_lng | Dropoff Locations Count | |
|---|---|---|---|
| 0 | 43.643481 | -79.399857 | 1 |
| 1 | 43.805779 | -79.518231 | 115 |
| 2 | 43.838713 | -79.315498 | 59 |
import numpy as np
import folium
# Plot the locations on a map
# Define center point for map
avg_lat = np.average(df[['collection_lat', 'dropoff_lat']].values.flatten())
avg_lng = np.average(df[['collection_lng', 'dropoff_lng']].values.flatten())
center = (avg_lat, avg_lng)
m = folium.Map(location=center, zoom_start=8.5)
# Define dropoff marker colours corresponding to each collection location
dropoff_colours =['green', 'orange', 'purple']
for collection_location_index, collection_location_row in collection_locations.iterrows():
# Plot collection locations with blue marker and icon colour corresponding to dropoff locations
filtered = df[df["collection_lat"] == collection_location_row['collection_lat']]
folium.Marker(location=(collection_location_row['collection_lat'], collection_location_row['collection_lng']),
icon=folium.Icon(icon='car', color='blue', icon_color=dropoff_colours[collection_location_index], prefix='fa'),
tooltip = str(collection_location_row['collection_lat']) + "," + str(collection_location_row['collection_lng'])).add_to(m)
#Plot dropoff locations in colours corresponding to source (i.e. collection location)
for index, row in filtered.iterrows():
folium.Marker(location=(row['dropoff_lat'], row['dropoff_lng']),
icon=folium.Icon(icon='map-pin', color=dropoff_colours[collection_location_index], prefix='fa'),
tooltip = str(row['dropoff_lat']) + "," + str(row['dropoff_lng'])).add_to(m)
m
# Arbitrarily pick the 3rd source and the locations at (43.8256628, -79.3993708) and (43.8543771, -79.4699297)
source = (collection_locations["collection_lat"].iloc[2], collection_locations["collection_lng"].iloc[2])
dest1 = (43.8256628, -79.3993708)
dest2 = (43.8543771, -79.4699297)
# Plot the locations for reference
m = folium.Map(location=source, zoom_start=12)
folium.Marker(location=source,icon=folium.Icon(color='purple',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=dest1,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=dest2,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
m
import geopandas as gpd
import osmnx
import math
#Load a geojson file created using geojson.io to define the graph boundaries (Dufferin-Major Mackenzie to Kennedy-Steeles)
boundary_geojson = gpd.read_file('q3_boundary.geojson')
graph = osmnx.graph_from_polygon(boundary_geojson.geometry[0], network_type='drive', simplify=True, clean_periphery=True)
# Plot the graph
osmnx.plot_graph(graph,figsize=(10,10))
(<Figure size 1000x1000 with 1 Axes>, <AxesSubplot: >)
import geopandas
# Find closest graph nodes to source and destinations
X = [source[1], dest1[1], dest2[1]]
Y = [source[0], dest1[0], dest2[0]]
closest_nodes = osmnx.distance.nearest_nodes(graph,X,Y)
# Get the rows from the Node GeoDataFrame
nodes, edges = osmnx.graph_to_gdfs(graph)
closest_rows = nodes.loc[closest_nodes]
# Put the nodes into a GeoDataFrame
od_nodes = geopandas.GeoDataFrame(closest_rows, geometry='geometry', crs=nodes.crs)
od_nodes
| y | x | highway | street_count | ref | geometry | |
|---|---|---|---|---|---|---|
| osmid | ||||||
| 319291881 | 43.836227 | -79.315404 | turning_circle | 1 | NaN | POINT (-79.31540 43.83623) |
| 446439005 | 43.825711 | -79.400226 | NaN | 3 | NaN | POINT (-79.40023 43.82571) |
| 297839692 | 43.853195 | -79.469145 | NaN | 3 | NaN | POINT (-79.46915 43.85319) |
# Plot map with original points (purple), graph vertices for navigation (red), and the graph
osmnx.folium.plot_graph_folium(graph, graph_map=m)
folium.Marker(location=source,icon=folium.Icon(color='purple',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=dest1,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=dest2,icon=folium.Icon(color='purple',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[0], od_nodes["x"].iloc[0]),icon=folium.Icon(color='red',icon='car', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[1], od_nodes["x"].iloc[1]),icon=folium.Icon(color='red',icon='map-marker', prefix='fa')).add_to(m)
folium.Marker(location=(od_nodes["y"].iloc[2], od_nodes["x"].iloc[2]),icon=folium.Icon(color='red',icon='map-marker', prefix='fa')).add_to(m)
m